在最一開始的時候，我們知道作業系統有一個很重要的目標，便是做到隔離性的部分，而隔離性這一部分的實作和虛擬記憶體管理有著很大的關係，以下將會介紹記憶體地址空間 (address space)，用來實現虛擬記憶體管理的硬體 (paging hardware)，以及在 xv6 中是如何實作出虛擬記憶體管理的。
在目前的電腦中，記憶體分成許多種，根據容量以及速度分成不同的層級，而這種模型被稱為記憶體階級模型 (memory hierarchy)，最上層速度最快，容量最小，價格最高。最下層速度最慢，容量最大，價格最低。
而在作業系統中，記憶體管理器 (memory manager) 實現記憶體分層的概念，記憶體管理器會記錄哪一些記憶體是正在使用的，哪一些是沒有在使用，能夠分配給 process 使用的，並在 process 結束後，將記憶體資源釋放。
在早期的電腦中，並不存在記憶體抽象化的想法，沒有虛擬記憶體或是 process (這裡指的是執行中的程式，沒有獨立記憶體空間)，每一個 process 可以直接存取物理記憶體地址，概念上如下
MOV R1, 10
將記憶體地址10當中的內容儲存到 R1 暫存器中，而假設我們要直接對記憶體 2000 的位置直接進行寫入，假設第二個 process 在記憶體地址2000的地方存有資料，第一個 process 直接對記憶體 2000 的操作是可行的，但這個行為可能導致第二個 process 直接當機 (crash)。
我們以圖像的形式來表示這一件事情，假設我們同時執行 Shell 和 cat
如果 Shell 不小心將記憶體地址 1500 存放到暫存器a0中，接著對 a0 進行寫入
sd $7, (a0)
這個行為等同於對記憶體 1500 的位置進行寫入，這樣便會發生因為 Shell 的錯誤行為導致 cat 當機的情況發生，因此程式的隔離性就被破壞了，我們需要一些機制來保證每一個程式之間的隔離性避免一個程式的錯誤行為導致其他執行中的程式受到影響。
在上面我們看到如果 process 能夠直接存取物理記憶體地址，可能會破壞掉其他的 process (除非有特殊的保護方式，像是在 IBM 360 中使用了一些存取保護機制)，而且在直接接觸到物理記憶體的條件下，我們也較難以讓多個 process 同時執行。
而這裡引進了 address space 的概念，直觀上就是讓每一個 process 都有自己的記憶體空間，cat 有自己的記憶體空間，從0到某一個最大值，Shell也有自己的記憶體空間，從0到某一個最大值。如果 Shell 往記憶體地址 1500 的地方寫入資料，他寫入的是自己 address space 的記憶體地址，而不是實體的記憶體地址，而如此我們就可以讓 Shell 無法去存取到自己 address space 範圍外的記憶體空間了。
而 address space 基本上就是虛擬記憶體的概念，可以直觀的想到虛擬記憶體和實體記憶體有一個轉換的機制，以及虛擬記憶體地址有可能比實體記憶體空間還要大的情況，實作上是什麼樣的情況，如果大量的 process 使用了虛擬記憶體，將物理記憶體地址空間全部使用完畢了，作業系統應該如何進行處理等等。
上面提及的 address space 的概念，最常見以及在 xv6 中實作的方法是使用了 Page Tables 的概念。
Page Tables 在硬體層面是通過了 CPU 以及記憶體管理單元 (memory management unit, MMU) 進行實作的，假設 CPU 執行任何 Fetch/Load/Store 等等指令，都是對虛擬記憶體地址進行操作，而不是對物理記憶體進行存取。虛擬記憶體會經過 MMU 轉換成物理記憶體地址的索引後，對物理記憶體地址進行載入資料或是寫入資料的操作。
一但我們啟用了 Paging (記憶體分頁) 的功能，執行每一條涉及記憶體操作的指令都是對虛擬記憶體地址進行操作，而這裡可以直觀的想到，MMU 會需要一張虛擬記憶體與物理記憶體轉換的表，其中一個欄位為虛擬記憶體地址，另外一個欄位為物理記憶體地址，而這一張表需要儲存在物理記憶體中的某一個位置，而 CPU 需要有一些暫存器用來得知這一張表所在的位置，而在前面有提及，在 RISC-V 架構中，CSR 中 satp 暫存器會儲存這一張表所在的位置，如此，CPU 便可以告知 MMU 可以從記憶體地址中哪一個位置找到虛擬記憶體地址和物理記憶體地址的轉換表了。
每一個 process 都有自己的記憶體分頁表，所以當 CPU 從一個 process 切換到另外一個 process 時，我們需要更新 CSR satp 的內容，讓 MMU 存取另外一張記憶體分頁表，如此，我們可以讓相同的虛擬記憶體地址映射到不同的實體物理記憶體地址。
在前面 xv6 的啟動與架構中，我們在 start.c 中的 start()看見了 satp CSR 對於 paging 的一些操作 (位於 supervisor mode 中，無法在 user mode 中修改 satp CSR，因為這樣就會破壞每一個 process 之間的隔離性了)，satp 會指向一張 page table (分頁表)，page table位於主記憶體中 (main memory) ，正在使用的 page table 會被 satp 所指向。
上圖為 satp 的結構，當 MODE 設置為0的時候，此時所有存取的記憶體地址都是實體記憶體地址，而當設置成8時，記憶體分頁 (paging) 的機制就會啟動，在 supervisor mode 和 user mode 底下存取的記憶體地址皆會是虛擬記憶體地址 (39 bit 的虛擬記憶體地址)，這些虛擬記憶體會需要經過 MMU 轉換，如果成功，將會變成56 bit 的實體記憶體地址。轉換失敗時會觸發異常 (page fault)，這是記憶體保護的機制。
假設每一個虛擬記憶體地址，都會對應到一個實體的記憶體地址，在 xv6 中暫存器為64 bit ，如此，我們會得到擁有欄位的記憶體分頁表，一張非常大張的表，而如果實作上如此將會耗費極大量的記憶體空間，下面將通過 RISC-V 來了解相關實作。
虛擬記憶體轉換 (Virtual Address Translation) 會在 supervisor mode 和 user mode 中保持開啟(在初始化後)，但是在初始化時我們會禁用這一項功能，在啟動與架構中，start.c 中 start() 可以看到我們將 satp 設置為0用來禁用 Paging。
在 supervisor mode 底下提供了虛擬記憶體系統 (Virtual Address System) ，將實體的物理記憶體劃分成許多張 page 提供記憶體保護的功能 (page 為一堆物理實體記憶體地址組成的區塊 (chunk)，為記憶體區塊的單位 )，以及虛擬記憶體轉換功能，而不是像是上面的概念，將每一條虛擬地址對應到一條物理地址，轉換是針對每一張 page (頁面)，在 RISC-V 中，每一張 page (頁面) 大小為 4KB。而無論是虛擬記憶體還是實體物理記憶體，都會對齊這個 page 的大小，概念上就是 0 ~ 4KB 為第0個物理/虛擬 page，4KB ~ 8KB 為第1個物理/虛擬 page。
有許多的 page table，而我們可以大致上分成兩個種類，一種是 kernel page table，所有的核心共享這一張 page table，另外一種為每一個在 user mode 的 process 所對應的 page table。
在RISC-V中支援了3種虛擬記憶體的轉換模式
所有對於主記憶體的操作，包含 Fetch/Load/Store，在啟用分頁 (pageing) 功能時，大多數都是對虛擬記憶體地址進行操作，要存取到實際物理記憶體地址，概念上應該要走訪 (walk) page table，通過走訪 page table 找到要存取的記憶體地址，但是在走訪 page table 的過程中，會涉及大量的存取記憶體操作，造成效能上的損失，而實際情況是我們會使用 Translation Lookaside Buffers (TLBs) 來存取，TLBs 為存在在核心中的暫存器，這個暫存器的功用是作為目前 page table 欄位的快取 (cache) ，而當我們切換了 page table，也就是 satp 暫存器中的內容發生改變，指向到我們切換的 page table，我們需要清除，清空 (flush) TLBs 的內容，在 RISC-V 中可以使用 sfence.vma來達成，而在 xv6 kernel 中，使用了 sfence_vma() 這個函式來完成，實際上這個函式是呼叫了RISC-V中的 sfence.vma 實作，可以在 kernel/riscv.h 中看見
static inline void
sfence_vma()
{
// the zero, zero means flush all TLB entries.
asm volatile("sfence.vma zero, zero");
}
下圖為 xv6 中 virtual address (xv39 virtual address)
總共使用 39 bits (9 + 9 + 9 + 12)，中間 27 bits 都會對應到一個 Page Table Entry (PTE)，可以當作是 index 的概念，用來查詢對應到的page，27 bits 所構成的域稱為 VPN (virtual page number)。每一個 PTE 會包含 44 bits 的 Physical Page Number 以及一些 bit 用來表示存取權限。
後面12 bits 為 offset，表示對應到 page 中哪一個 byte。而之所以為12 bits 原因為 page 大小為4096 byte，，能夠讓我們在一個 page 中通過這12 bits 的 offset 來走訪到特定的 page 記憶體位置。
所以整個虛擬記憶體地址到物理記憶體地址的翻譯為讀取 virtual address 中間27 bits 得到記憶體分頁的 index，這個 index 對應到了物理記憶體中某一段4KB，接著讀取 virtual address 後面12 bits，該12 bits 為對應到的記憶體分頁的 offset，假設offset 為 a，則我們可以通過 virtual address 中間 27 bits 找到記憶體分頁的起始記憶體地址，再加上 virtual address 後面12 bits，offset的部分，就可以找到實體物理記憶體地址了，如此便完成了虛擬記憶體地址到實體物理記憶體地址的轉換。
在虛擬記憶體中，中間27 bits 為 PPN (Physical Page Number)，不僅可以用來查詢到物理頁面的 index，還能夠查到一組 flag，用來表示存取權限，而這一些 flag 和 index 所組成的物件，稱為一個 PTE。
下圖為sv39 Page Table Entry (PTE)的結構
最右方 D, A, G, U, X, W, R, V 控制是否能夠存取，而在 xv6 中只有使用 U, X, W, R, V，相關的定義定義在kernel/riscv.h中
#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access
而中間的 PPN[2], PPN[1]. PPN[0]，總共 44 bits，PPN 為 Physical Page Number 的縮寫，MMU 會將 virtual address 39 bits 中高位27位 bits 對應到某一個 PTE (也就是上方 index 查詢到 page 的概念)，因此大約有個，並將該 PTE 的 PPN 加上virtual address的低位12 bits兩者相加作為實體記憶體地址 (physical address)，而我們可以從上面轉換關係得知實體記憶體地址的長度為44 + 12 = 56 bits，如下圖所示
sv39 物理記憶體地址 :
而整個轉換過程如下圖所示
from xv6 book
而當我們無法順利將虛擬記憶體地址轉換成實體記憶體地址時，就會產生出 page fault，這時候系統會從硬碟中相應的地方將硬碟分頁載入到記憶體，然後重新執行一次轉換。
上方我們知道虛擬記憶體到實體物理記憶體是以 page 作為單位，而我們又知道每一個 process 都有自己的 page table，page table 中 27 bit 對應到了一個個 PTE，總共有個，這是一個很大的數字，實際上不會像是走訪具有
個元素的陣列來找到對應的 PTE，為了加速搜尋速度以及空間上的優化，這裡使用到了樹狀結構。
如上面說到，最簡單實作 page table 的方式為線性走訪的方式，類似於陣列的實作，將物理記憶體地址 (存放在PTE內) 由低到高，虛擬記憶體分頁表 (VPN) 編號由0開始遞增儲存在記憶體內。
每一個 PTE 大小為64 bits，假設編號0號的 VPN 對應到一個 PTE，而我們知道在 sv 39的虛擬記憶體中，VPN 域佔有27 bits，每一個 bits 對應到一個 PTE，因此如此總共會有個 PTE 和 VPN 的對應關係所組成的欄(entry)，假設對於某一個 process 的 page table，從物理記憶體空間的 base_addr 開始，則如下圖所示
我們可以試著計算 prcess A，page table的大小，大小為，一個 process 就需要使用1GB 的記憶體，就空間使用上我們不可能這樣設計，即便這樣的設計可以讓 kernel 的控制以及 MMU 設計變得十分的簡單。
而優化上可以思考，每一個 VPN 會對應到一個 PTE，而 PTE 會有一個 flag 讓 MMU 判斷是否能夠進行虛擬記憶體地址到物理記憶體地址的轉換，在最一開始的時候，一個 process 的 address space 是空的，也就是每一個 PTE都是 invaild 的，而後面經過 kernel 分配好記憶體空間後，再開始從0以一個 page 為單位，讓 PTE 變成 vaild，MMU 得以轉換，而 process 對應到的page table 占用的實體記憶體空間也跟著增加。概念上，也就是按照 process 對於記憶體的需求進行分配。
在每一個 process 對應的 page table 中間27 bit，實際上是由3個9 bit的欄位所組成，分別為 L2, L1, L0，可以直接當作是樹狀結構，L2 對應到樹的 level 0，以此類推。最一開始的9個 bit，用來作為Page Directory (分頁目錄) 的索引，Page Directory 的大小也是 4KB，和 page 相同，每一個 Page Directory 對應到一條 PTE，PTE 大小為 64 bits，所以一張 Page Directory 總共有 個 PTE (概念上 Page Directory 為一張表，索引到其他的 Page Directory 或是 Page table，但實際上 Page table 和 Page Directory 沒有那麼明顯的區分)。
想像 L2, L1, L0 為一棵字典樹所組成的結構，在一般字典樹中，每一層的節點是由 A ~ Z 所組成，也就是每一層有26個節點，而在這裡，每一層有512個節點，而這是一顆高度為3的樹，每一個節點都指向一張 Page Direcotry，而我們在走訪時，即是走訪到Page Direcotry，通過 PPN 得到記憶體分頁的位置，每一個節點內部的 Page Direcotry 都是一個能夠線性查詢的資料結構，可能是陣列等等。以圖表示如下:
所以，satp CSR 會指向到最高層級 (level 0) 的 Page directory 的物理記憶體地址，而 Page directory 的實作上也是 sv 39 的結構，因此 satp CSR 指向 Page directory，我們就可以得到一個 PPN 了，而 PPN 會指向到下一個層級 (level 1) 的 Page directory，
而當我們在 level 1 的 Page directory 時，通過 L1 的部分就可以完成 indexing 了，接著通過 level 1 Page directory 的 PPN 走訪到 level 2 Page directory。
在 level 2 Page directory 時，通過 L0 完成 indexing，在level 2 Page directory 時，可以通過 PPN 得到虛擬記憶體地址對應到的實體物理記憶體地址。
而以上我們通過了3步驟的走訪，得到了實際的記憶體地址，而假設某一個 process 只使用了一個 page，4KB，如下
在level 0 時，我們需要一條 PTE，該 PTE 指向到 level 1的 page directory，而由於我們只需要一條 PTE，因此在 level 0我們只需要一張 page directory。
而在 level 1，我們需要一條 PTE 指向到 level 2的 page directory，而此時我們只需要一條 PTE，因此在 level 1我們只需要一張 page directory。
在 level 2，我們指向到物理記憶體 USE 的位置，也就是一個 PTE，需要一張 page directory。
因此我們總共使用了3張 page directory，總共有條 PTE。
而如果我們直接將 L2, L1, L0當做一張 page directory，則我們會產生出條 PTE，相比起樹狀結構多出了不少的空間。
SiFive FU540-C000 Manual v1p0
xv6-riscv
Operating System Concepts, 9/e
RISC-V xv6 Book
iThome鐵人賽
看影片追技術